package com.stephen.data.search;

import java.util.ArrayList;
import java.util.List;

/**
 * @author: stephen
 * @create: 2020-02-01 10:31
 * @description: 二分查找
 * 必须是有序数组
 */
public class BinarySearch {

    public static void main(String[] args) {
        int[] arr = {0,1,2,2,2,2,3,4,5};
        // int index = binarySearch(arr, 0, arr.length - 1, -5);
        // System.out.println("index=" + index);
        List<Integer> index = binarySearch2(arr, 0, arr.length - 1, 2);
        System.out.println("index=" + index);
    }

    /**
     * 普通二分查找,查找的值在数组中只有一个
     * @param arr 原数组
     * @param left 最左边索引
     * @param right 最右边索引
     * @param findValue 要找的值
     * @return 找到,返回索引,找不到,返回-1
     */
    public static int binarySearch(int[] arr,int left,int right,int findValue) {

        // 没有找到,也要退出,否则会出现死循环
        // 假定有序,从小到大,如果超出最小最大值,可提前结束
        if (left > right || findValue < arr[0] || findValue > arr[arr.length - 1]) {
            return -1;
        }

        int mid = (left + right) / 2;
        int midValue = arr[mid];

        if (findValue > midValue) { // 向右找
            return binarySearch(arr,mid + 1,right,findValue);
        } else if (findValue < midValue) { // 向左找
            return binarySearch(arr,left,mid - 1,findValue);
        } else {
            return mid;
        }
    }

    /**
     * 找多个相同元素
     * @param arr
     * @param left
     * @param right
     * @param findValue
     * @return 返回一个集合,没有找到,就是空集合
     */
    public static List<Integer> binarySearch2(int[] arr, int left, int right, int findValue) {

        // 没有找到,也要退出,否则会出现死循环
        // 假定有序,从小到大,如果超出最小最大值,可提前结束
        if (left > right || findValue < arr[0] || findValue > arr[arr.length - 1]) {
            return new ArrayList<>();
        }

        int mid = (left + right) / 2;
        int midValue = arr[mid];

        if (findValue > midValue) { // 向右找
            return binarySearch2(arr,mid + 1,right,findValue);
        } else if (findValue < midValue) { // 向左找
            return binarySearch2(arr,left,mid - 1,findValue);
        } else {
            // 找到第一个mid时,不要马上返回
            // 1.向mid的左边扫描,将所有满足条件的下标,加入集合中
            // 2.向mid的右边扫描,将所有满足条件的下标,加入集合中
            // 3.返回list
            List<Integer> list = new ArrayList<>();

            int temp = mid - 1;
            while (true) {
                if (temp < 0 || arr[temp] != findValue) {
                    break;
                }
                // 左边的所有索引
                list.add(temp);
                temp -= 1;
            }
            // 中间的索引
            list.add(mid);
            temp = mid + 1;
            while (true) {
                if (temp > arr.length - 1 || arr[temp] != findValue) {
                    break;
                }
                list.add(temp);
                temp += 1;
            }
            return list;
        }
    }


}
